package com.changhong;

/**
 * Created by Administrator on 2018/12/12
 */
public class SortQuickTreeWays {

    public static void main(String[] args) {
//        int[] data = new int[] {10, 8, 9, 5, 5, 2, 5, 2, 7, 7};
        int[] data = genData(20);
        print(data);
        sort(data);
        print(data);
    }

    static class Position {
        private int lt;

        public int getLt() {
            return lt;
        }

        public void setLt(int lt) {
            this.lt = lt;
        }

        public int getGt() {
            return gt;
        }

        public void setGt(int gt) {
            this.gt = gt;
        }

        private int gt;
    }

    private static void sort(int[] data) {
        sort(data, 0, data.length - 1);
    }


    private static void sort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        Position position = partition(data, left, right);
        sort(data, left, position.getLt());
        sort(data, position.getGt(), right);
    }

    private static Position partition(int[] data, int left, int right) {
        Position position = new Position();
        int randomSelect = (int) (Math.random() * (right - left + 1)) + left;
        swap(data, left, randomSelect);
        int value = data[left];

        position.setLt(left);
        position.setGt(right + 1);

        int index = position.getLt();

        while (index < position.getGt()) {
            if (data[index] < value) {
                swap(data, position.getLt() + 1, index);
                position.setLt(position.getLt() + 1);
                index++;
            } else if (data[index] > value) {
                swap(data, position.getGt() - 1, index);
                position.setGt(position.getGt() - 1);
            } else {
                index++;
            }
        }

        return position;
    }


    public static void print(int[] data) {
        if (data == null) return;
        for (int i = 0; i < data.length; i++) {
            if (i < data.length - 1) {
                System.out.print(String.format("%02d", data[i]) + " ");
            } else {
                System.out.println(String.format("%02d", data[i]));
            }
        }
    }

    public static int[] genData(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = (int) (Math.random() * 100);
        }
        return data;
    }

    public static void swap(int[] data, int x, int y) {
        int length = data.length;
        if (x < 0 || y < 0 || x > length - 1 || y > length - 1)
            throw new IllegalArgumentException();

        int temp = data[x];
        data[x] = data[y];
        data[y] = temp;
    }
}
